package com.fyl.basic_algorithm.stringMatch;

import java.util.Arrays;

/**
 * @author 冯永龙
 * @date 2021/4/5 22:34
 */
public class Trie {
    private TrieNode root = new TrieNode('/');  //储存无意义的字符

    public TrieNode getRoot() {
        return root;
    }

    // 往Trie树中插入一个字符串
    public void insert(char[] text) {
        TrieNode p = this.root;
        for (int i = 0; i < text.length; i++) {
            // 通过字符的 ASCII 码减去“a”的 ASCII 码，迅速找到匹配的子节点的指针。
            int index = text[i] - 'a';
            if (p.children[index] == null) {
                //将下一个字符装入p的子节点中
                TrieNode newNode = new TrieNode(text[i]);
                p.children[index] = newNode;
            }
            //将指针指向下一个字符
            p = p.children[index];
        }
        //此时p已经是最后一个字符
        p.isEndingChar = true;
    }

    // 在Trie树中查找一个字符串
    public boolean find(char[] pattern) {
        TrieNode p = this.root;
        for (int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 'a';
            if (p.children[index] == null) {
                return false; //不存在pattern
            }
            p = p.children[index];
        }

        if (p.isEndingChar == false) {  //不完全匹配，只是前缀
            return false;
        } else {  //找到pattern
            return true;
        }
    }

    @Override
    public String toString() {
        return "Trie{" +
                "root=" + root +
                '}';
    }

    static class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndingChar = false;

        @Override
        public String toString() {
            return "TrieNode{" +
                    "data=" + data +
                    ", children=" + Arrays.toString(children) +
                    ", isEndingChar=" + isEndingChar +
                    '}';
        }

        public TrieNode(char data) {
            this.data = data;
        }
    }
}

 class Test {
     public static void main(String[] args) {
         Trie trie = new Trie();
         char[] c = {'a','b','c'};
         trie.insert(c);
         System.out.println(trie.toString());
         System.out.println(trie.find(c));
     }
}
